/**
 * // Definition for a Node.
 * function Node(val, children) {
 *    this.val = val;
 *    this.children = children;
 * };
 */
/* N叉树的前序遍历 */
/**
 * @param {Node|null} root
 * @return {number[]}
 */
/* 递归 */
var preorder = function (root) {
	const res = []
	helper(root, res)
	return res
}
const helper = (root, res) => {
	if (root == null) return
	res.push(root.val)
	for (const ch of root.children) {
		helper(ch, res)
	}
}
/* 迭代 */
var preorder = function (root) {
	if (root == null) return []
	const ans = []
	const st = []
	const nextIndex = new Map()
	let node = root
	while (st.length || node) {
		while (node) {
			ans.push(node.val)
			st.push(node)
			if (!node.children) break
			nextIndex.set(node, 1)
			node = node.children[0]
		}
		node = st[st.length - 1]
		const i = nextIndex.get(node)
		if (i < node.children.length) {
			nextIndex.set(node, i + 1)
			node = node.children[i]
		} else {
			st.pop()
			nextIndex.delete(node)
			node = null
		}
	}
	return ans
}
/* 迭代优化 */
var preorder = function (root) {
	const res = []
	if (root == null) return res
	const stack = [root]
	while (stack.length) {
		const node = stack.pop()
		res.push(node.val)
		for (let i = node.children.length - 1; i >= 0; i--) {
			stack.push(node.children[i])
		}
	}
	return res
}
